package com.mlh.binarytree;

/**
 * @author 缪林辉
 * @date 2024/8/27 11:16
 * @DESCRIPTION
 */
//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
public class 二叉树的最近公共祖先 {
    //后序遍历
    //自己思考的时候卡在了递归的返回值要返回什么
    //这里返回的就是节点  用null来判断
    //这个返回值还可以解决 p 或者 q本身是两者最近公共祖先的情况
    public TreeNode method1(TreeNode root, TreeNode p, TreeNode q) {
        return recursion(root,p,q);
    }

    private TreeNode recursion(TreeNode root, TreeNode p, TreeNode q) {
        if(root==p||root==q||root==null){
            return root;
        }
        TreeNode left = recursion(root.left, p, q);
        TreeNode right = recursion(root.right, p, q);
        if(left!=null&&right!=null){
            return root;
        }
        return left!=null?left:right;
    }

    public TreeNode practice(TreeNode root, TreeNode p, TreeNode q) {
        return recursionPractice(root,p,q);
    }

    private TreeNode recursionPractice(TreeNode node, TreeNode p, TreeNode q) {
        if(node==null||node==p||node==q){
            return node;
        }
        TreeNode left=recursionPractice(node.left,p,q);
        TreeNode right=recursionPractice(node.right,p,q);
        if(left!=null&&right!=null){
            return node;
        }
        return left==null?right:left;
    }
}
